package com.tgy.programmer_code_interview_guide._02_linkedList;

import lombok.val;

/**
 * @Author: tgy
 * @Date: 1/28/21 11:53 AM
 */
public class _14_向有序的环形单链表中插入新节点 {

    public static Node circleInsertVal(Node root,int val){

        Node dummyNode = new Node();
        dummyNode.next = root;
        Node preNode = dummyNode,lastNode = null;

        Node node = root;

        while (true) {

            if (node.val < val) {

                preNode = node;
            }
            lastNode = node;
            node = node.next;
            if (node == root) {

                break;
            }
        }

        Node newNode = new Node(val);

        newNode.next = preNode.next;
        preNode.next = newNode;

        if (preNode == dummyNode) {

            lastNode.next = dummyNode.next;
        }

        return dummyNode.next;
    }

    public static void main(String[] args) {

        Node root = Nodes.generalNode(new int[]{1, 2, 2, 3, 4, 4, 5}, true);

        Node root3 = circleInsertVal(root, 6);
        root3 = circleInsertVal(root,0);
        Node node = root3;

        while (true) {

            System.out.println(node.val);
            node = node.next;
            if (node == root3) {
                break;
            }
        }

    }
}
